package singlelist;

import listinterface.IList;
import myexception.ListIndexOutOfBoundsException;

/**
 * @Author 12629
 * @Description：
 */
public class Test {

    public static MySingleList.ListNode mergeTwoLists(MySingleList.ListNode headA,
                                               MySingleList.ListNode headB) {

        //定义一个 傀儡节点(虚拟节点)：头节点   此时涉及到了 获取静态内部类对象
        MySingleList.ListNode newH = new MySingleList.ListNode(-1);

        MySingleList.ListNode tmp= newH;

        while (headA != null && headB != null) {
            if(headA.val < headB.val) {
                tmp.next = headA;
                headA = headA.next;
                //tmp = tmp.next;
            }else {
                tmp.next = headB;
                headB = headB.next;
                //tmp = tmp.next;
            }
            tmp = tmp.next;
        }
        if(headA != null) {
            tmp.next = headA;
        }
        if(headB != null) {
            tmp.next = headB;
        }
        return newH.next;
    }

    public static MySingleList.ListNode getIntersectionNode(MySingleList.ListNode headA,
                                                     MySingleList.ListNode headB) {


        //1. 假定 A链表长  B链表短
        MySingleList.ListNode pl = headA;
        MySingleList.ListNode ps = headB;

        //2.分别求两个链表的长度

        int len1 = 0;
        int len2 = 0;
        while (pl != null) {
            len1++;
            pl = pl.next;
        }

        while (ps != null) {
            len2++;
            ps = ps.next;
        }
        pl = headA;
        ps = headB;

        //3. 求长度的差值 len

        //len < 0   -->  pl = headB  ps = headA len = len2 - len1
        int len = len1 - len2;
        if(len < 0) {
            pl = headB;
            ps = headA;
            len = len2 - len1;
        }
        //4. 确定 pl指向的链表 一定是长 链表   ps指向的节点 一定是短链表

        //5.让pl走 len步
        while (len != 0) {
            pl = pl.next;
            len--;
        }

        //6. ps 和 pl 同时走 直到相遇
        while (pl != ps) {
            pl = pl.next;
            ps = ps.next;
        }

        //如果没有相遇 那么pl == null
        if(pl == null) {
            return null;
        }
        return pl;
    }

    public static void createCut(MySingleList.ListNode headA,
                                 MySingleList.ListNode headB) {

        headB.next.next = headA.next.next.next;
    }

    public static void main(String[] args) {
        MySingleList mySingleList1 = new MySingleList();
        mySingleList1.addLast(12);
        mySingleList1.addLast(23);
        mySingleList1.addLast(34);
        mySingleList1.addLast(45);
        mySingleList1.addLast(56);
        mySingleList1.addLast(67);
        mySingleList1.display();
        System.out.println("==============");

        mySingleList1.createLoop();

        ///mySingleList1.display(); 死循环

        boolean hasCycle = mySingleList1.hasCycle();
        System.out.println(hasCycle);
    }

    public static void main6(String[] args) {
        MySingleList mySingleList1 = new MySingleList();
        mySingleList1.addLast(12);
        mySingleList1.addLast(23);
        mySingleList1.addLast(34);
        mySingleList1.addLast(45);
        mySingleList1.addLast(56);
        mySingleList1.addLast(67);
        mySingleList1.display();
        System.out.println("==============");
        MySingleList mySingleList2 = new MySingleList();
        mySingleList2.addLast(13);
        mySingleList2.addLast(25);
        mySingleList2.addLast(35);
        mySingleList2.addLast(146);
        mySingleList2.addLast(156);
        mySingleList2.display();
        System.out.println("==============");

        System.out.println("========测试======");
        createCut(mySingleList1.head,mySingleList2.head);

        MySingleList.ListNode ret = getIntersectionNode(mySingleList1.head,mySingleList2.head);

        System.out.println(ret.val);
    }

    public static void main5(String[] args) {
        MySingleList mySingleList1 = new MySingleList();
        mySingleList1.addLast(12);
        mySingleList1.addLast(23);
        mySingleList1.addLast(34);
        mySingleList1.addLast(45);
        mySingleList1.addLast(56);
        mySingleList1.addLast(67);
        mySingleList1.display();
        System.out.println("==============");
        MySingleList mySingleList2 = new MySingleList();
        mySingleList2.addLast(13);
        mySingleList2.addLast(25);
        mySingleList2.addLast(35);
        mySingleList2.addLast(146);
        mySingleList2.addLast(156);
        mySingleList2.display();
        System.out.println("==============");

        System.out.println("========合并======");

        MySingleList.ListNode ret = mergeTwoLists(mySingleList1.head,mySingleList2.head);

        mySingleList2.display(ret);
    }

    public static void main4(String[] args) {
        MySingleList mySingleList = new MySingleList();
        mySingleList.addLast(12);
        mySingleList.addLast(23);
        mySingleList.addLast(34);
        mySingleList.addLast(45);
        mySingleList.addLast(56);
        mySingleList.addLast(67);
        mySingleList.display();

        System.out.println(mySingleList.kthToLast(13));

        /*singlelist.MySingleList.ListNode node = mySingleList.middleNode();
        if(node == null) {
            System.out.println("链表为空...");
        }else {
            System.out.println(node.getVal());
        }*/
        //singlelist.MySingleList.ListNode node = mySingleList.reverseList();
        //mySingleList.display(node);
    }

    public static void main3(String[] args) {
        IList mySingleList = new MySingleList();
        mySingleList.addLast(23);
        mySingleList.addLast(23);
        mySingleList.addLast(23);
        mySingleList.addLast(23);
        mySingleList.display();

//        mySingleList.removeAllKey(23);
        mySingleList.clear();
        mySingleList.display();
        System.out.println(mySingleList.size());
    }

    public static void main2(String[] args) {
        IList mySingleList = new MySingleList();
        mySingleList.addLast(12);
        mySingleList.addLast(23);
        mySingleList.addLast(34);
        mySingleList.addLast(45);
        mySingleList.addFirst(100);
        mySingleList.display();

        try {
            mySingleList.addIndex(3,99);
        }catch (ListIndexOutOfBoundsException e) {
            e.printStackTrace();
        }

        mySingleList.display();
    }

    public static void main1(String[] args) {
        MySingleList mySingleList = new MySingleList();
        mySingleList.createList();
        mySingleList.display();
        boolean contains = mySingleList.contains(56);
        System.out.println(contains);
        //System.out.println(mySingleList.size());
    }
}
